package code1_100.code20_30;

import java.util.Stack;

/**
 * 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
 * <p>
 * 有效字符串需满足：
 * <p>
 * 左括号必须用相同类型的右括号闭合。
 * 左括号必须以正确的顺序闭合。
 * 输入：s = "()[]{}"
 * 输出：true
 * <p>
 * 输入：s = "([)]"
 * 输出：false
 */
public class _20isVaild {

    public static void main(String[] args) {
        System.out.println(isValid("{[]}"));
    }

    /**
     * 正常的入栈出栈操作
     *
     * 执行用时：3 ms, 在所有 Java 提交中击败了25.36% 的用户
     * 内存消耗：36.4 MB, 在所有 Java 提交中击败了89.49% 的用户
     *
     * @param s
     * @return
     */
    public static boolean isValid(String s) {
        if(s.length()==0){
            return true;
        }
        if(s.length()%2!=0){
            return false;
        }
        Stack<Character> stack = new Stack<>();
        stack.push(s.charAt(0));
        Character temp;
        for (int i = 1; i < s.length(); i++) {
            temp = s.charAt(i);
            if(stack.empty()){
                stack.push(temp);
            }else if(isMatch(stack.peek(),temp)){
                stack.pop();
            }else {
                stack.push(temp);
            }
        }
        return stack.empty();
    }

    public static boolean isMatch(char a,char b){

        if(a=='('&&b==')'){
            return true;
        }else if(a=='['&&b==']'){
            return true;
        }else if(a=='{'&&b=='}'){
            return true;
        }else {
            return false;
        }
    }

}
